import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public void reorderList1(ListNode head) {
        //找到链表中间节点
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = null;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        //逆序后半部分的链表
        ListNode tmpHead = new ListNode();
        ListNode cur = fast == null ? slow : slow.next;
        if (cur == slow) {
            prev.next = null;
        } else {
            slow.next = null;
        }
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = tmpHead.next;
            tmpHead.next = cur;
            cur = next;
        }

        //合并链表
        ListNode newHead = new ListNode();
        ListNode curA = head;
        ListNode curB = tmpHead.next;
        ListNode tail = newHead;
        while (curA != null && curB != null) {
            tail.next = curA;
            ListNode next = curA.next;
            curA.next = curB;
            tail = curB;
            curA = next;
            curB = curB.next;
        }
        tail.next = curA == tmpHead.next ? curB : curA;
        head = newHead.next;
    }

    public void reorderList(ListNode head) {
        //处理边界情况
        if (head == null || head.next == null || head.next == null) return;

        //1.找链表的中间节点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //2.把slow后面的部分给逆序
        ListNode head2 = new ListNode();
        ListNode cur = slow.next;
        slow.next = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }

        //3.合并两个链表
        ListNode cur1 = head, cur2 = head2.next;
        ListNode ret = new ListNode();
        ListNode prev = ret;
        while (cur1 != null) {
            //先放第一个链表
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;

            //在合并第二个链表
            if (cur2 != null) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }

    //合并k个升序链表 使用小根堆
    public ListNode mergeKLists1(ListNode[] lists) {
        ListNode head = new ListNode();
        int k = lists.length;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });
        for (int i = 0; i < k; i++) {
            if (lists[i] != null) {
                queue.add(lists[i]);
            }
        }

        ListNode tail = head;
        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            System.out.println(cur.val);
            tail.next = cur;
            tail = cur;
            if (cur.next != null) {
                queue.add(cur.next);
            }
        }

        return head.next;
    }


    //合并k个升序链表 使用递归和归并排序的思路
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeSort(lists, 0, lists.length - 1);
    }

    private ListNode mergeSort(ListNode[] lists, int left, int right) {
        if (left > right) return null;
        if (left == right) return lists[left];
        int mid = (left + right) / 2;
        //[left,mid] [mid+1,right]
        ListNode headA = mergeSort(lists, left, mid);
        ListNode headB = mergeSort(lists, mid + 1, right);

        ListNode head = new ListNode(), tail = head;
        ListNode curA = headA, curB = headB;
        while (curA != null && curB != null) {
            if (curA.val < curB.val) {
                tail.next = curA;
                curA = curA.next;
                tail = tail.next;
            } else {
                tail.next = curB;
                curB = curB.next;
                tail = tail.next;
            }
        }
        tail.next = curA == null ? curB : curA;
        return head.next;
    }

    // k个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        //计算要逆序的组数n
        int n = 0;
        ListNode cur = head;
        while(cur!=null) {
            cur = cur.next;
            n++;
        }
        n/=k;

        ListNode newHead = new ListNode();
        ListNode tail = newHead,tmp = newHead;
        cur = head;
        //翻转n组
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<k;j++) {
                ListNode next = cur.next;
                cur.next = tail.next;
                tail.next = cur;
                if(j==0) tmp = cur;
                cur = next;
            }
            tail = tmp;
        }

        tail.next = cur;

        return newHead.next;
    }

    public void test() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        ListNode node8 = new ListNode(8);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;

        ListNode ret = reverseKGroup(node1,3);
    }

}

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.test();
    }
}
